/*
选择排序

基本思想:
首先，找到数组中最小的那个元素
其次，将它和数组的第一个元素交换位置(如果第一个元素就是最小元素那么它就和自己交换)。
接着，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。
如此往复，直到将整个数组排序。这种方法我们称之为选择排序。

具体步骤:
1.首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
2.再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3.重复第二步，直到所有元素均排序完毕。

最好时间复杂度：O(N2)
最坏时间复杂度：O(N2)
平均时间复杂度：O(N2)
空间复杂度：O(1)

稳定排序：否
原地排序：是

*/


#include "../../include/common.h"


int FindMin(ElementType arr[], int n, int min){
    int i;
    for (i=min; i<n; i++){
        if (arr[i] < arr[min])
            min = i;
    }
    return min;
}


int FindMax(ElementType arr[], int n, int max){
    int i;
    for (i=max; i<n; i++){
        if (arr[i] > arr[max])
            max = i;
    }
    return max;
}


// 升序
void SelectSort(ElementType arr[], int n){
    int i;
    int target;
    for (i=0; i<n-1; i++){
        // 从 i+1 开始查找无序序列中的最小值下标
        target = FindMin(arr, n, i+1);
        // 交换元素
        if (target != i){
            Swap(arr, i, target);
        }
    }
}


/**
 * 改进：
 *  每趟循环确认两个元素
*/
void SelectSort2(ElementType arr[], int n){
    int i, j;
    int min, max;

    for (i=0; i<(n-1)/2; i++){
        min = i;
        max = n-1-i;
        // 从 i+1 开始查找无序序列中的最值下标
        for (j=i+1; j<n-i; j++){
            if (arr[j] < arr[min])
                min = j;
            if (arr[j] > arr[max])
                max = j;
        }
        // 交换元素
        if (min != i){
            Swap(arr, i, min);
        }
        if (max != n-1-i){
            Swap(arr, n-1-i, max);
        }
    }
}